#!/usr/bin/env python3
"""
贪心算法实时资源拾取策略
任务3：玩家视野受限于周围3×3区域，每次移动时优先选择视野内"性价比"最高的资源

核心算法：
- 视野限制：玩家只能看到周围3×3区域的资源
- 贪心选择：每次选择视野内单位距离收益最大的资源
- 实时决策：不需要全局信息，适合动态环境
- 路径生成：逐步生成资源拾取路径

特性：
- 模拟真实游戏体验（视野受限）
- 快速实时决策（O(1)每步）
- 适应动态资源环境
- 可视化拾取过程
"""

import json
import math
from typing import List, Tuple, Dict, Optional, Set
from collections import deque


class GreedyResourceCollector:
    """贪心算法实时资源拾取器"""
    
    def __init__(self, vision_range: int = 1):
        """
        初始化资源拾取器
        
        参数：
        vision_range: 视野范围，1表示3×3区域（玩家位置±1）
        """
        self.vision_range = vision_range
        self.maze: Optional[List[List[str]]] = None
        self.size = 0
        self.resources: Dict[Tuple[int, int], int] = {}
        self.traps: List[Tuple[int, int]] = []
        self.player_pos: Optional[Tuple[int, int]] = None
        self.collected_resources: List[Tuple[Tuple[int, int], int]] = []
        self.path: List[Tuple[int, int]] = []
        self.total_score = 0
        
    def setup_environment(self, 
                         maze_matrix: List[List[str]], 
                         resources: Dict[Tuple[int, int], int],
                         traps: List[Tuple[int, int]],
                         start_pos: Tuple[int, int]):
        """
        设置游戏环境
        
        参数：
        maze_matrix: 迷宫矩阵
        resources: 全部资源分布（但玩家视野受限）
        traps: 陷阱位置
        start_pos: 玩家起始位置
        """
        self.maze = maze_matrix
        self.size = len(maze_matrix)
        self.resources = resources.copy()  # 复制以便修改
        self.traps = traps
        self.player_pos = start_pos
        self.collected_resources = []
        self.path = [start_pos]
        self.total_score = 0
        
        print(f"🎮 贪心资源拾取器初始化:")
        print(f"   视野范围: {self.vision_range*2+1}×{self.vision_range*2+1}")
        print(f"   迷宫大小: {self.size}×{self.size}")
        print(f"   总资源数: {len(resources)}")
        print(f"   陷阱数量: {len(traps)}")
        print(f"   起始位置: {start_pos}")
        
    def get_vision_area(self, pos: Tuple[int, int]) -> List[Tuple[int, int]]:
        """
        获取玩家视野范围内的所有位置
        
        参数：
        pos: 玩家当前位置
        
        返回：
        视野内可达位置列表
        """
        assert self.maze is not None
        x, y = pos
        vision_positions = []
        
        for dx in range(-self.vision_range, self.vision_range + 1):
            for dy in range(-self.vision_range, self.vision_range + 1):
                nx, ny = x + dx, y + dy
                
                # 检查边界
                if 0 <= nx < self.size and 0 <= ny < self.size:
                    # 检查是否可通过（不是墙壁）
                    if self.maze[nx][ny] != '#':
                        vision_positions.append((nx, ny))
                        
        return vision_positions
    
    def get_visible_resources(self, pos: Tuple[int, int]) -> List[Tuple[Tuple[int, int], int]]:
        """
        获取视野内的所有可用资源
        
        参数：
        pos: 玩家当前位置
        
        返回：
        [(资源位置, 资源价值), ...] 列表
        """
        vision_area = self.get_vision_area(pos)
        visible_resources = []
        
        for resource_pos, value in self.resources.items():
            if resource_pos in vision_area:
                visible_resources.append((resource_pos, value))
                
        return visible_resources
    
    def calculate_resource_efficiency(self, player_pos: Tuple[int, int], 
                                    resource_pos: Tuple[int, int], 
                                    resource_value: int) -> float:
        """
        计算资源的性价比（单位距离收益）
        
        参数：
        player_pos: 玩家位置
        resource_pos: 资源位置
        resource_value: 资源价值
        
        返回：
        性价比值（价值/距离）
        """
        # 使用曼哈顿距离
        distance = abs(player_pos[0] - resource_pos[0]) + abs(player_pos[1] - resource_pos[1])
        
        # 避免除零错误，相同位置距离设为1
        if distance == 0:
            distance = 1
            
        # 考虑陷阱惩罚
        efficiency = resource_value / distance
        
        # 如果资源位置是陷阱，降低性价比
        if resource_pos in self.traps:
            efficiency -= 3 / distance  # 陷阱惩罚
            
        return efficiency
    
    def find_path_to_resource(self, start: Tuple[int, int], 
                            target: Tuple[int, int]) -> Optional[List[Tuple[int, int]]]:
        """
        使用BFS找到从起点到目标的最短路径
        
        参数：
        start: 起始位置
        target: 目标位置
        
        返回：
        路径列表，如果无法到达返回None
        """
        assert self.maze is not None
        if start == target:
            return [start]
            
        queue = deque([(start, [start])])
        visited = {start}
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            current_pos, path = queue.popleft()
            
            for dx, dy in directions:
                next_pos = (current_pos[0] + dx, current_pos[1] + dy)
                
                # 检查边界和可通过性
                if (0 <= next_pos[0] < self.size and 
                    0 <= next_pos[1] < self.size and
                    next_pos not in visited and
                    self.maze[next_pos[0]][next_pos[1]] != '#'):
                    
                    new_path = path + [next_pos]
                    
                    if next_pos == target:
                        return new_path
                        
                    queue.append((next_pos, new_path))
                    visited.add(next_pos)
                    
        return None  # 无法到达
    
    def get_possible_moves(self, pos: Tuple[int, int]) -> List[Tuple[int, int]]:
        """
        获取位置的所有可能移动方向
        
        参数：
        pos: 当前位置
        
        返回：
        可移动位置列表
        """
        assert self.maze is not None
        x, y = pos
        possible_moves = []
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 检查边界和可通过性
            if (0 <= nx < self.size and 
                0 <= ny < self.size and
                self.maze[nx][ny] != '#'):
                possible_moves.append((nx, ny))
                
        return possible_moves
    
    def greedy_collect_resources(self, max_exploration_steps: int = 50) -> Tuple[int, List[Tuple[int, int]]]:
        """
        使用贪心算法收集资源
        
        算法流程：
        1. 扫描当前视野内的所有资源
        2. 如果有资源：计算性价比，选择最优资源
        3. 如果无资源：探索移动（随机选择可通行方向）
        4. 重复直到达到最大探索步数或无法移动
        
        参数：
        max_exploration_steps: 最大探索步数，防止无限循环
        
        返回：
        (总得分, 完整路径)
        """
        assert self.player_pos is not None
        assert self.maze is not None
        
        print(f"\n🔍 开始贪心资源收集...")
        step_count = 0
        exploration_steps = 0
        
        while step_count < max_exploration_steps:
            step_count += 1
            current_pos = self.player_pos
            assert current_pos is not None
            
            # 获取视野内的资源
            visible_resources = self.get_visible_resources(current_pos)
            
            if visible_resources:
                # 有资源时使用贪心策略
                exploration_steps = 0  # 重置探索计数
                print(f"   第{step_count}步: 位置{current_pos}，发现{len(visible_resources)}个资源")
                
                # 计算每个资源的性价比
                best_resource = None
                best_efficiency = float('-inf')
                best_path = None
                
                for resource_pos, resource_value in visible_resources:
                    efficiency = self.calculate_resource_efficiency(
                        current_pos, resource_pos, resource_value
                    )
                    
                    # 找到到达该资源的路径
                    path_to_resource = self.find_path_to_resource(current_pos, resource_pos)
                    
                    if path_to_resource and efficiency > best_efficiency:
                        best_efficiency = efficiency
                        best_resource = (resource_pos, resource_value)
                        best_path = path_to_resource
                        
                if best_resource is None:
                    print(f"   无可达资源，开始探索")
                    continue
                    
                # 移动到最佳资源
                resource_pos, resource_value = best_resource
                
                # 更新路径（排除起始位置以避免重复）
                if best_path and len(best_path) > 1:
                    self.path.extend(best_path[1:])
                    
                # 收集资源
                self.resources.pop(resource_pos)  # 从可用资源中移除
                self.collected_resources.append((resource_pos, resource_value))
                
                # 更新得分
                score_change = resource_value
                if resource_pos in self.traps:
                    score_change -= 3
                    
                self.total_score += score_change
                self.player_pos = resource_pos
                
                print(f"     → 选择资源{resource_pos}(价值{resource_value}, 性价比{best_efficiency:.2f})")
                print(f"     → 当前得分: {self.total_score}")
                
            else:
                # 无资源时进行探索移动
                exploration_steps += 1
                print(f"   第{step_count}步: 位置{current_pos}，视野内无资源，开始探索 (探索步数: {exploration_steps})")
                
                # 获取可移动的相邻位置
                possible_moves = self.get_possible_moves(current_pos)
                
                if not possible_moves:
                    print(f"   无可移动位置，探索结束")
                    break
                    
                # 简单探索策略：选择未访问过的位置，或随机选择
                visited_positions = set(self.path)
                unvisited_moves = [pos for pos in possible_moves if pos not in visited_positions]
                
                if unvisited_moves:
                    # 优先选择未访问位置
                    next_pos = unvisited_moves[0]
                    print(f"     → 探索新位置: {next_pos}")
                else:
                    # 随机选择已访问位置（可能发现新资源）
                    import random
                    next_pos = random.choice(possible_moves)
                    print(f"     → 重访位置: {next_pos}")
                
                # 移动到选择的位置
                self.path.append(next_pos)
                self.player_pos = next_pos
                
                # 检查移动位置是否是陷阱
                if next_pos in self.traps:
                    self.total_score -= 3
                    print(f"     ⚠️  踩到陷阱! 位置{next_pos}, 得分-3 (当前得分: {self.total_score})")
                
                # 防止过度探索
                if exploration_steps > 10:
                    print(f"   探索步数过多，结束探索")
                    break
            
        print(f"\n✅ 贪心收集完成！总得分: {self.total_score}，路径长度: {len(self.path)}")
        return self.total_score, self.path
    
    def visualize_collection_process(self) -> List[List[str]]:
        """
        可视化资源收集过程
        
        返回：
        可视化后的迷宫矩阵
        """
        assert self.maze is not None
        
        # 深拷贝原始迷宫
        visual_matrix = [row[:] for row in self.maze]
        
        # 标记路径
        path_positions = set(self.path)
        
        for pos in self.path:
            x, y = pos
            if pos == self.path[0]:  # 起点
                visual_matrix[x][y] = 'S'
            elif pos == self.path[-1]:  # 终点
                visual_matrix[x][y] = 'E'
            else:
                visual_matrix[x][y] = '●'
                
        # 标记收集的资源
        for resource_pos, value in self.collected_resources:
            x, y = resource_pos
            if value >= 10:
                visual_matrix[x][y] = 'H'  # 高价值资源
            elif value >= 6:
                visual_matrix[x][y] = 'G'  # 中价值资源
            else:
                visual_matrix[x][y] = 'R'  # 低价值资源
                
        # 标记未收集的资源（半透明显示）
        for resource_pos, value in self.resources.items():
            x, y = resource_pos
            if (x, y) not in path_positions:
                visual_matrix[x][y] = '◦'  # 未收集资源
                
        # 标记陷阱
        for trap_pos in self.traps:
            x, y = trap_pos
            if (x, y) in [pos for pos, _ in self.collected_resources]:
                visual_matrix[x][y] = 'T'  # 踩到的陷阱
                
        return visual_matrix
    
    def print_collection_analysis(self):
        """打印详细的收集分析"""
        print(f"\n📊 贪心算法收集分析")
        print(f"   算法类型: 局部最优贪心策略")
        print(f"   视野限制: {self.vision_range*2+1}×{self.vision_range*2+1}")
        print(f"   决策原则: 单位距离收益最大")
        
        print(f"\n🎯 收集成果:")
        print(f"   总得分: {self.total_score}")
        print(f"   收集资源数: {len(self.collected_resources)}")
        print(f"   路径长度: {len(self.path)} 步")
        
        if self.collected_resources:
            print(f"\n📦 收集顺序:")
            for i, (pos, value) in enumerate(self.collected_resources, 1):
                trap_mark = " (陷阱)" if pos in self.traps else ""
                print(f"   {i:2d}. 位置{pos}: +{value}分{trap_mark}")
                
        # 性价比分析
        if self.collected_resources and len(self.path) > 1:
            avg_efficiency = self.total_score / (len(self.path) - 1)
            print(f"\n⚡ 效率指标:")
            print(f"   平均步收益: {avg_efficiency:.2f} 分/步")
            print(f"   贪心决策次数: {len(self.collected_resources)}")
            
        # 剩余资源分析
        remaining_resources = len(self.resources)
        if remaining_resources > 0:
            remaining_value = sum(self.resources.values())
            print(f"\n💔 未收集资源:")
            print(f"   剩余数量: {remaining_resources}")
            print(f"   剩余价值: {remaining_value}")
            print(f"   (由于视野限制未发现)")


def load_maze_from_json(filename: str) -> List[List[str]]:
    """从JSON文件加载迷宫"""
    with open(filename, 'r', encoding='utf-8') as f:
        data = json.load(f)
    return data['maze']


def demo_greedy_collection():
    """演示贪心算法资源收集"""
    print("=== 贪心算法实时资源拾取演示 ===\n")
    
    collector = GreedyResourceCollector(vision_range=1)  # 3×3视野
    
    # 测试7×7迷宫
    print("【测试案例1】7×7迷宫 - 视野受限资源收集")
    try:
        maze_7x7 = load_maze_from_json('perfect_maze_7x7.json')
        
        # 分散放置资源测试贪心策略
        resources_7x7 = {
            (1, 3): 8,    # 起点附近高价值
            (2, 2): 3,    # 中等距离中价值
            (3, 5): 12,   # 远距离超高价值
            (4, 1): 5,    # 另一个方向
            (5, 3): 6,    # 靠近某个路径
        }
        
        traps_7x7 = [
            (2, 3),       # 阻挡高价值资源
            (4, 5),       # 随机陷阱
        ]
        
        collector.setup_environment(
            maze_matrix=maze_7x7,
            resources=resources_7x7,
            traps=traps_7x7,
            start_pos=(1, 1)
        )
        
        # 执行贪心收集
        total_score, collection_path = collector.greedy_collect_resources()
        
        # 可视化结果
        visual_matrix = collector.visualize_collection_process()
        print(f"\n🗺️  贪心收集路径可视化:")
        print("   图例: S=起点, E=终点, R/G/H=已收集资源, ◦=未收集资源, T=陷阱, ●=路径")
        for row in visual_matrix:
            print('   ' + ''.join(f'{cell:>2}' for cell in row))
            
        # 详细分析
        collector.print_collection_analysis()
        
    except FileNotFoundError:
        print("7×7迷宫文件未找到")
        
    print(f"\n" + "="*60)
    
    # 测试15×15迷宫
    print("\n【测试案例2】15×15迷宫 - 大规模视野受限测试")
    try:
        maze_15x15 = load_maze_from_json('perfect_maze_15x15.json')
        
        # 大规模资源分布
        resources_15x15 = {
            (2, 2): 4,    (3, 8): 7,    (5, 5): 9,
            (7, 3): 6,    (8, 9): 12,   (10, 7): 5,
            (11, 11): 15, (12, 4): 8,   (6, 12): 10,
        }
        
        traps_15x15 = [
            (2, 3), (7, 4), (9, 9), (11, 10)
        ]
        
        collector_large = GreedyResourceCollector(vision_range=1)
        collector_large.setup_environment(
            maze_matrix=maze_15x15,
            resources=resources_15x15,
            traps=traps_15x15,
            start_pos=(1, 1)
        )
        
        # 执行大规模贪心收集
        total_score_large, path_large = collector_large.greedy_collect_resources()
        
        # 简化分析（避免输出过长）
        print(f"\n📈 大规模测试结果:")
        print(f"   总得分: {total_score_large}")
        print(f"   收集资源数: {len(collector_large.collected_resources)}")
        print(f"   路径长度: {len(path_large)} 步")
        print(f"   贪心效率: {total_score_large/len(path_large):.3f} 分/步")
        
        remaining = len(collector_large.resources)
        print(f"   未发现资源: {remaining} 个 (视野限制)")
        
    except FileNotFoundError:
        print("15×15迷宫文件未找到")


if __name__ == "__main__":
    demo_greedy_collection()
    
    print(f"\n✅ 贪心算法实时资源拾取完成！")
    print(f"🎮 核心特性验证:")
    print(f"   • 3×3视野限制 ✓")
    print(f"   • 单位距离收益最大化 ✓") 
    print(f"   • 实时局部决策 ✓")
    print(f"   • 适应动态环境 ✓") 